Skip to main content

Microsoft Research Video

More than 1,100 brilliant scientists and engineers push the boundaries of computing in multiple research areas and include contributions to Kinect for Xbox 360, work to develop an HIV vaccine, and advancing education techniques in rural communities.

PART OF
Computers & Technology
More right-solid
More right-solid
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
SHOW DETAILS
up-solid down-solid
eye
Title
Date Archived
Creator
An evolutionarily stable strategy (ESS) is an equilibrium strategy that is immune to invasions by rare alternative ('mutant') strategies. Unlike Nash equilibria, ESS do not always exist in finite games. In this paper, we address the question of what happens when the size of the game increases: does an ESS exist for 'almost every large' game? Letting the entries in the n x n game matrix be randomly chosen according to an underlying distribution F, we study the number of ESS with support of size...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Sergiu Hart
Microsoft Research Video
movies
eye 31
favorite 0
comment 0
We study random walks on the uniform spanning tree (UST) on Z 2 . We obtain estimates for the transition probabilities of the random walk, the distance of the walk from its starting point after n steps, and exit times of both Euclidean balls and balls in the intrinsic graph metric. In particular, we prove that the spectral dimension of the uniform spanning tree on Z 2 is 16/13 almost surely. In order to prove these results, we use the work of Barlow, Jarai, Kumagai, Misumi and Slade on random...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Robert Masson
We provide a sufficient condition for the continuity of real valued permanental processes.When applied to the subclass of permanental processes which consists of squares of Gaussian processes, we obtain the sufficient condition for continuity which is also known to be necessary. Using an isomorphism theorem of Eisenbaum and Kaspi which relates Markov local times and permanental processes, we obtain a general sufficient condition for the joint continuity of the local times. We show that for...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Jay Rosen
Microsoft Research Video
movies
eye 16
favorite 0
comment 0
We will present the proof of a conjecture of B. Nienhuis on the number ofself-avoiding walks on the honeycomb lattice. More precisely, we will provethat the connective constant of the lattice equals the square root of (2+√2).This theorem is the first step towards a deeper understanding of self-avoiding walks. Wewill state some conjectures on the scaling-limit behavior of these walks. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Hugo Duminil-Copin
Microsoft Research Video
movies
eye 19
favorite 0
comment 0
A well known conjecture asserts that on any graph the random walk and the interchange process have the same spectral gap.I will present recent work in collaboration with T.M. Liggett and T. Richthammer, in which we prove the conjecture using a recursive strategy. The main novelty is an idea based on electric network reduction, which allows us to reduce the problem to the proof of anew comparison inequality between certain weighted graphs. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Pietro Caputo
When agents have conflicting preferences over a set of alternatives and they want to make a joint decision, a natural way to do so is by voting. How to design and analyze desirable voting rules has been studied by economists for centuries. In recent decades, technological advances, especially those in the Internet economy, have introduced many new applications for voting theory. For example, we can rate movies based on people’s preferences, as done on many movie recommendation sites. However,...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Lirong Xia
Microsoft Research Video
movies
eye 18
favorite 0
comment 0
We close the problem of understanding the space complexity of pth moment estimation in data streams for 0 p = 2 by giving the first optimal upper and lower bounds. In this problem, a high-dimensional vector receives a long sequence of coordinate-wise updates, and we must output a low relative-error approximation of the pth moment at the end of the stream while keeping a memory footprint exponentially smaller than the vector length. This problem has applications in network traffic monitoring,...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Jelani Nelson
In recent years, the emergence of massive computing tasks that arise in context of web applications and networks has made the need for efficient graph algorithms more pressing than ever. In particular, it lead us to focus on reducing the running time of the algorithms to make them as fast as possible, even if it comes at a cost of reducing the quality of the returned solution. This motivates us to expand our algorithmic toolkit to include techniques capable of addressing this new challenge. In...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Aleksander Madry
The talk focuses on expander graphs in conjunction with the combined use of SDPs and eigenvalue techniques for approximating optimal solutions to combinatorial optimization problems. In the first part of the talk I will explain how to construct cost-effective, expanding networks by using 'local' sparsifiers of graphs that emerge as a solution to a semidefinite program. In the second part of the talk I will show that the Unique Games Conjecture is false when the underlying constraint graph is a...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Alexandra Kolla
Microsoft Research Video
movies
eye 49
favorite 0
comment 0
We study the following model for mobile wireless networks. At time 0, nodes are distributed as a Poisson point process with intensity λ over R 2 . We let nodes move independently in continuous time according to Brownian motion, and assume that at any time two nodes can exchange message iff their current distance is at most 1. In contrast with the case of static networks, where the network is usually required to be connected (and therefore limited to a finite region of R 2 ), in a mobile...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Alexandre Stauffer
We discuss several fascinating concepts and algorithms in graph theory that arose in the design of a nearly-linear time algorithm for solving diagonally-dominant linear systems. We begin by defining a new notion of what it means to approximate a graph by another graph, and explain why these sparse approximations enable the fast solution of linear equations. To build these sparsifiers, we rely on low-stretch spanning trees, random matrix theory, spectral graph theory, and graph partitioning...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Dan Alan Spielman
This is a two-part talk. In the first part, we prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only pairs of cards. In the second part, we use the theorem to obtain improved bounds for two previously studied models. Our first application is the following shuffle introduced by Thorp in 1973. Suppose the number of cards n is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Ben Morris
Microsoft Research Video
movies
eye 78
favorite 0
comment 0
Khot's Unique Games Conjecture (UGC) is one of the most central open problems in computational complexity theory. UGC asserts that for a certain constraint satisfaction problem, it is NP-hard to decide whether there is a labeling that satisfies almost all the constraints or, for every labeling, the fraction of the constraints satisfied is very small. Since its origin, the UGC has been applied with remarkable success to prove tight hardness of approximation results for several important NP-hard...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Alexandra Kolla
Microsoft Research Video
movies
eye 39
favorite 0
comment 0
Planar maps are embeddings of connected planar graphs in the plane considered up to continuous deformation. We will present a “master bijection” for planar maps and show that it can be specialized in various ways in order to count several families of maps. More precisely, for each integer d we obtain a bijection between the family of maps of girth d and a family of decorated plane trees. This gives new counting results for maps of girth d counted according to the degree distribution of...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Olivier Bernardi
We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices with edge weights chosen independently and uniformly at random from [0,1] is O(n 2 ) , in expectation and with high probability. This resolves a long standing open problem. Joint work with Y. Peres, D. Sotnikov and U. Zwick ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Benny Sudakov
Microsoft Research Video
movies
eye 27
favorite 0
comment 0
Nash equilibrium, integer factorization, and stable configuration of a Hopfield net are examples of total functions, problems in NP that are guaranteed to always have solutions. Each such problem is an implicit existence theorem; consequently, total functions are categorized by the elementary argument involved in the proof of the theorem: Pigeonhole principle, parity argument, conservation of degree, or potential function (no other kinds are known...). We will survey this area, and introduce a...
Topics: Microsoft Research, Microsoft Research Video Archive, Nikhil Devanur and Yuval Peres, Christos...
I will briefly recall the connection between the Sparsest Cut problem in graphs and low-distortion embeddings of finite metric spaces into L 1 . Then I will talk about a recent approach to lower bounds pioneered by Cheeger and Kleiner (2006), following a conjecture we made with Naor (2003). The main idea is to develop a differentiation theory for L 1 -valued mappings. I will discuss a discrete version of this theory (following Eskin-Fisher-Whyte and Lee-Raghavendra). I will then construct a...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, James Lee
Microsoft Research Video
movies
eye 18
favorite 0
comment 0
Myerson has argued that the Nash equilibrium lies at the foundations of modern economic thought, and yet the dark computational side of the concept keeps getting gloomier. We show that playing games under considerations of risk, disambiguating games via equilibrium selection a`-la Harsanyi-Selten, and computing equilibria by the homotopy method, are all rife with very serious complexity impediments. Joint work with Paul Goldberg and Amos Fiat. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Christos Papadimitriou
Microsoft Research Video
movies
eye 66
favorite 0
comment 0
Let C 1 denote the largest connected component of the critical Erdos-Renyi random graph G(n,1/n). We show that, typically, the diameter of C 1 is of order n 1/3 and the mixing time of the lazy simple random walk on C 1 is of order n. The latter answers a question of Benjamini, Kozma and Wormald. These results extend to clusters of size n 2/3 of p-bond percolation on any d-regular n-vertex graph where such clusters exist, provided that p(d-1) ≤ 1 + O(n -1/3 ). Joint work with Yuval Peres....
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Asaf Nachmias
Microsoft Research Video
movies
eye 27
favorite 0
comment 0
We study the k -core of a random (multi) graph on n vertices with a given degree sequence. We let n tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the k -core is empty, and other conditions that imply that with high probability the k -core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Malwina Luczak
Microsoft Research Video
movies
eye 19
favorite 0
comment 0
Consider a repeated two-person game. The question is how much smarter a player must be in order to effectively predict the moves of the other player. The answer depends on the formal definition of effective prediction, the number of actions each player has in the stage game, as well as on the measure of smartness. Effective prediction means that, no matter what the stage-game payoff function, the player can play (with high probability) a best reply in most stages. Neyman and Spencer [4] provide...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Abraham Neyman
Microsoft Research Video
movies
eye 42
favorite 0
comment 0
We consider network contribution games, where each agent in a social network has a budget of effort that it can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Elliot Anshelevich
Microsoft Research Video
movies
eye 28
favorite 0
comment 0
We consider the Max-Min Allocation problem, in which we are given a set of m agents and a set of n items, together with utilities u(A,i) of agent A for item i. Our goal is to allocate items to agents to maximize fairness. Specifically, the utility of an agent is the sum of its utilities for the items it receives, and we seek to maximize the minimum utility of any agent. While this problem has received much attention, its approximability has not been well-understood thus far: the best previously...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Julia Chuzhoy
Microsoft Research Video
movies
eye 65
favorite 0
comment 0
In this talk we will demonstrate iterative methods as a general technique to analyze linear programming formulations of combinatorial optimization problems. We first show an application of the method to the Minimum Bounded Degree Spanning Tree problem. We present a polynomial time algorithm that returns a spanning tree of optimal cost while exceeding the degree bound of any vertex by at most an additive one. This is the best possible result for this problem and settles a 15-year-old conjecture...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Mohit Singh
Most combinatorial optimization problems of interest are NP-hard to solve exactly. To cope with this intractability, one settles for approximation algorithms with provable guarantee on the quality of approximation. Despite great success in designing approximation algorithms, underlying a vast majority of the work is the technique of linear programming, or more generally semi-definite programming. This poses the natural question: How far can we push the technique of semi-definite programming?...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Prasad Nagaraj Raghavendra
Microsoft Research Video
movies
eye 128
favorite 0
comment 0
Given a point process M of intensity one in the plane, the well-known Voronoi tesselation assigns a polygon (of different area) to each point of M. The geometry of 'fair' allocations (assigning unit area to each point of M) is richer and more mysterious: see http://www.math.ubc.ca/~holroyd/stable.html There is a unique 'fair' allocation that is 'stable' in the sense of the Gale-Shapley stable marriage problem, every point of M is assigned a bounded region with finitely many components, but...
Topics: Microsoft Research, Microsoft Research Video Archive, Scott Sheffield, Yuval Peres
Microsoft Research Video
by Microsoft Research
movies
eye 20
favorite 0
comment 0
There is an increasing demand for the analysis of large amounts of data of many different kinds. Often the data isequipped with a notion of distance, reflecting notions of similarity of the data. Further, it is often the case that the notion of similarityis not backed up by theoretical constructions, but simply reflects an investigator's intuitive notion of similarity. This means thatin studying the data set, one should perform analyses which have some degree of robustness to small changes in...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Gunnar Carlsson
Microsoft Research Video
movies
eye 49
favorite 0
comment 0
Consider percolation on the Hamming cube 0,1 n at the critical probability p c (at which the expected cluster size is 2 n/3 ). It is known that if p=p c (1+O(2 -n/3 ), then the largest component is of size roughly 2 2n/3 with high probability and that this quantity is non-concentrated. We show that for any sequence eps(n) such that eps(n)2 -n/3 and eps(n)=o(1) percolation at p c (1+eps(n)) yields a largest cluster of size (2+o(1))eps(n)2 n . This result settles a conjecture of Borgs, Chayes,...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Asaf Nachmias
This is a two-part talk. In the first part, we prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only pairs of cards. In the second part, we use the theorem to obtain improved bounds for two previously studied models. Our first application is the following shuffle introduced by Thorp in 1973. Suppose the number of cards n is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Ben Morris
Microsoft Research Video
movies
eye 51
favorite 0
comment 0
2:00 - 2:30 Olle Häggström (Chalmers) Percolation, mass transport and cluster indistinguishability 2:35 - 3:05 Yuval Peres (Microsoft) Connectivity Probability in Critical Percolation: An unpublished gem from Oded ©2009 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, David Wilson, Yuval Peres, Prasad Tetali,...
Microsoft Research Video
by Microsoft Research
movies
eye 41
favorite 0
comment 0
See http://www.math.ubc.ca/~holroyd/sort for pictures. Joint work with Omer Angel, Dan Romik and Balint Virag. Sorting a list of items is perhaps the most celebrated problem in mathematical computer science. If one must do this by swapping neighboring pairs, the worst initial condition is when the n items are in reverse order, in which case n choose 2 swaps are needed. A sorting network is any sequence of n choose 2 swaps which achieves this. We investigate the behavior of a uniformly random...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Alexander E. Holroyd
We present an algorithm for the sparsest cut problem that simultaneously achieves the better approximation factor of SDP/multicommodity-flow based algorithms and the subquadratic running time of single-commodity flow based algorithms. The idea is that we can turn Arora, Rao, and Vazirani's matching-chaining argument into an algorithm for finding good augmenting paths in a multicommodity flow network. Our analysis follows ARV's, making essential use of measure concentration on the sphere. ©2010...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Jonah Sherman
Microsoft Research Video
movies
eye 25
favorite 0
comment 0
The multiple intents re-ranking problem was introduced recently by Azar, Gamzu and Xin (STOC 2009) in the context of ordering results of a web search query. In this problem, we are given a universe of elements U and a collection of subsets S1,S2,..,Sm. Additionally, each set S has a covering requirement of K(S). The goal is to order the elements in U to minimize average covering time of a set, where set S is said to be covered at time t, if t is the earliest time at which K(S) elements from S...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Nikhil Bansal
Technology continues to move in the direction of parallel computation, whether it be in a computer or across the internet. Second order effects such as the communication needed to carry out a distributed algorithm have become a concern. In this light, we take an information theoretic look at the fundamental communication requirements in networks for distributing tasks. The model is simple: tasks are numbered; some nodes in the network are assigned tasks; others have to choose from the remaining...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Paul Cuff
Sixty years ago, at the Institute for Advanced Study in Princeton, New Jersey, a 32 x 32 x 40-bit matrix of 24-microsecond random access memory was undergoing initial tests. John von Neumann (1903-1957) succeeded in jump-starting the digital revolution by bringing engineers into the den of the mathematicians, rather than by bringing mathematicians into a den of engineers. This implementation of Alan Turing’s Universal Machine broke the distinction between numbers that mean things and numbers...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, George Dyson
Microsoft Research Video
movies
eye 48
favorite 0
comment 0
There exists an entropy-preserving equivariant surjective map from the d-dimensional critical sandpile model to a certain closed, shift-invariant subgroup of the Cartesian product of infinitely many cycles, one for each node of the d-dimensional integer lattice (the 'harmonic model'). A similar map can be constructed for the dissipative abelian sandpile model and be used to prove uniqueness and the Bernoulli property of the measure of maximal entropy for that model. (Joint work with Evgeny...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Klaus Schmidt
Microsoft Research Video
movies
eye 25
favorite 0
comment 0
We will present Talagrand's majorizing measure theory, which gives tight estimates for maxima of Gaussian processes, including the full proof and an extension to a weak version of the Bernoulli conjecture. This is the second lecture in a series specifically designed to be accessible to beginners in the field. The format will be informal and questions will be encouraged Further lectures will be scheduled later to discuss more advanced aspects. ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, James Lee
Microsoft Research Video
movies
eye 34
favorite 0
comment 0
We will present Talagrand's majorizing measure theory, which gives tight estimates for maxima of Gaussian processes, including the full proof and an extension to a weak version of the Bernoulli conjecture. This is the third lecture in a series specifically designed to be accessible to beginners in the field. The format will be informal and questions will be encouraged ©2010 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, James Lee
Microsoft Research Video
movies
eye 15
favorite 0
comment 0
The dynamical system in the repeated play of a game is 'uncoupled' if each player initially knows only his own payoff function. We study the effects of this natural assumption on the possibility and impossibility of reaching Nash and correlated equilibria, and on the communication complexity that is involved. ©2007 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Sergiu Hart
Microsoft Research Video
by Microsoft Research
movies
eye 11
favorite 0
comment 0
For Markov random fields temporal mixing, the time it takes for the Glauber dynamics to approach it's stationary distribution, is closely related to the spatial mixing properties of the measure such as uniqueness and the reconstruction problem. Such questions are of importance in probability, statistical physics and theoretical computer science. I will survey some recent progress in understanding the mixing time of the Glauber dynamics as well as related results on spatial mixing. ©2009...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Allan Sly
Microsoft Research Video
movies
eye 44
favorite 0
comment 0
We discuss a recent technique for dealing with k-independent families of random variables. The basic idea in showing that F is fooled by k-independence is to approximate by a smooth function F~ and note that the expectation of the Taylor polynomials are determined by k-independence. F~ can be obtained by convolving F with the Fourier transform of a compactly supported bump function. We discuss the development of this technique, leading up to the proof that limited independence fools degree 2...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Daniel Kane
Microsoft Research Video
movies
eye 53
favorite 0
comment 0
In this talk I shall sketch some results Oliver Riordan of Oxford and I have obtained on the critical probabilities in percolation. The story starts with Scullard and Zi, who recently pointed out that a broad class of planar percolation models are self-dual. They stated that in a variety of classes of models depending on a parameter, the parameter giving self-duality is the critical value for percolation. However, noticing self-duality is simply the starting point: the mathematical difficulty...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Bela Bollobas
Microsoft Research Video
movies
eye 62
favorite 0
comment 0
The Abelian sandpile growth model is a deterministic diffusion process for configurations of chips on the integer lattice. I will discuss joint work with Wesley Pegden on the scaling limit of the stable configurations. ©2011 Microsoft Corporation. All rights reserved.
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Charles Smart
Microsoft Research Video
movies
eye 8
favorite 0
comment 0
How can we efficiently aggregate rankings, cut a graph into two parts with many edges between them, pack items into bins, cluster items using pairwise similarity information, route vehicles in the Euclidean plane, or construct a Steiner tree in a planar graph? All these examples of optimization problems are NP-hard, yet, under some mild assumptions, they all have near-optimal solutions that can be computed in (high) polynomial time. I will present a few algorithmic techniques and their...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Claire Mathieu
Talk 1: 3:30 to 4:15 Title: Probabilistic Approximation Theorems in Game Theory and Stochastic Optimization Speaker: Costis Daskalakis, MIT Abstract: In Economics, reliability theory and other domains, uncertainty is often modeled assuming Bayesian knowledge about unknown parameters. This assumption enables important results, e.g. Nash's theorem on the existence of equilibria in randomized strategies in games, and Myerson's theorem on revenue-optimal auctions. On the other hand, stochastic...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Costis Daskalakis and Jason...
More than twenty years ago, Manickam, Miklos, and Singhi conjectured that for any integers n ≥ 4k , every set of n real numbers with nonnegative sum has at least binom n-1k-1 k -element subsets whose sum is also nonnegative. In this talk we discuss the connection of this problem with matchings and fractional covers of hypergraphs, and with the question of Feige and Samuels on estimating the probability that the sum of nonnegative independent random variables exceeds its expectation by a given...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Benny Sudakov
Microsoft Research Video
movies
eye 39
favorite 0
comment 0
By a classical theorem of Marstrand, if X is a set in the plane then almost every linear projection of X onto a line has the largest possible dimension, i.e. min1,dim(X). However, in general the dependence of this number on the projection is quite bad and is not well understood even in very simple examples. In joint work with Pablo Shmerkin we show that for a large class of fractals which arise from arithmetic, dynamical or combinatorial constructions there is some semi-continuity in the...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Michael Hochman
Microsoft Research Video
movies
eye 10
favorite 0
comment 0
The Gaussian central limit theorem says that for a wide class of stochastic systems, the bell curve (Gaussian distribution) describes the statistics for random fluctuations of important observables. In this talk I will look beyond this class of systems to a collection of probabilistic models which include random growth models, polymers,particle systems, matrices and stochastic PDEs, as well as certain asymptotic problems in combinatorics and representation theory. I will explain in what ways...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Ivan Corwin
“It is not from the benevolence of the butcher, the brewer, or the baker,that we expect our dinner, but from their regard for their own interest.”Each participant in a competitive economy is “led by an invisible hand topromote an end which was no part of his intention.” Adam Smith, 1776.With his treatise, The Wealth of Nations, 1776, Adam Smith initiated the field of economics,and his famous quote provided this field with its central guiding principle. The pioneeringwork of Walras...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Vijay V Vazirani
Microsoft Research Video
movies
eye 42
favorite 0
comment 0
Understanding Gibbs measures on trees and their spatial mixing thresholds (uniqueness, strong spatial mixing, reconstruction) can give insight into the behavior of Gibbs measures on general graphs, in particular random graphs which are locally tree-like. We discuss two results: In the first result, we show that counter to the general notion that the d regular tree is the worst case for decay of correlation between sets and nodes among all d regular graphs, we produce an example of a spin...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Allan Sly
Microsoft Research Video
movies
eye 183
favorite 0
comment 0
In 1999 A. Barabasi and R. Albert suggested the idea of preferential attachment to explain the power law distribution of the vertex degrees in web graphs. Several mathematical models have then appeared incorporating this idea. Among them, the LCD model by B. Bollobas and O. Riordan, the Buckley--Osthus model, the Bollobas--Borgs-Chayes--Riordan model of directed scale-free graphs, etc. Many deep results have been obtained concerning these models. For example, one studies the degree...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Andrey Raigorodsky
Microsoft Research Video
by Microsoft Research
movies
eye 32
favorite 0
comment 0
We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random algorithm by keeping the accumulated rounding errors as small as possible.Our new algorithm surprisingly closely approximates the idealized process (where the tokens are divisible) on important network topologies. On d-dimensional torus graphs with n nodes it deviates from the idealized process only by an additive...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Tobias Friedrich
Microsoft Research Video
movies
eye 29
favorite 0
comment 0
Consider the standard Ising model on a finite n x n grid at low temperature. If the boundary spins are held fixed equal to +1 it is believed that the mixing time of the corresponding Glauber dynamics (Gibbs sampler) is poly(n). Although such a result is still far from being proved, recently there has been some exciting progress using the censoring inequality by Peres and P. Winkler together with inductive schemes. The final outcome is a quasi-poly(n) bound valid for all temperatures below the...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Fabio Martinelli
We consider the stochastic evolution of a (1 + 1)-dimensional polymer in the depinned regime. At equilibrium the system exhibits a double well structure: the polymer lies(essentially) either above or below the repulsive line. As a consequence one expects a metastable behavior with rare jumps between the two phases combined with a fast thermalization inside each phase. However the energy barrier between these two phases is only logarithmic in the system size L and therefore the two relevant time...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Fabio Toninelli
Microsoft Research Video
movies
eye 14
favorite 0
comment 0
A number of data sets are naturally described in matrix form. Examples range from microarrays to collaborative filtering data, to the set of pairwise distances of a cloud of points. In many of these examples, singular value decomposition (SVD) provides an efficient way to construct a low-rank approximation thus achievieng both dimensionality reduction, and effective denoising. SVD is also an important tool in the design of approximate linear algebra algorithms for massive data sets. It is a...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Andrea Montanari
Microsoft Research Video
movies
eye 51
favorite 0
comment 0
We model situations in which a principal provides incentives to a groupof agents to participate in a project (such as a social event, commercialactivity or the adoption of a certain technological standartization).Agents' benefits from participation depend on the identity of otherparticipating agents. We assume bilateral externalities and characterize theoptimal incentive mechanism. Using a graph-theoretic approach we show thatthe optimal mechanism provides a ranking of incentives for the...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Eyal Winter
Part 1: 'The Communication Complexity of Uncoupled Nash Equilibrium Procedures', by Sergiu Hart and Yishay Mansour http://www.ma.huji.ac.il/hart/abs/comcom.html We study the question of how long it takes players to reach a Nash equilibrium in 'uncoupled' setups, where each player initially knows only his own payoff function. We derive lower bounds on the number of bits that need to be transmitted in order to reach a Nash equilibrium, and thus also on the required number of steps. These lower...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Sergiu Hart
Microsoft Research Video
movies
eye 38
favorite 0
comment 0
Consider a random Galton-Watson tree conditioned to have size n.We assume that the offspring distribution has mean 1 and finite variance, but no further moment conditions.It is well-known that the width and height both are of the order n 1/2 (see for example Aldous (1991) for much more detailed results on the shape). I will talk about about proving tail estimates, for example P(width > k) < exp(-c k 2 /n). (Note that no such exponential tail bounds are assumed for the offspring...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Svante Janson
Microsoft Research Video
movies
eye 89
favorite 0
comment 0
Let C n be the n’th generation in the construction of the middle-half Cantor set. The Cartesian square K n of C n consists of 4 n squares of side-length 1/(4 n ). The chance that a long needle thrown at random in the unit square will meet K n is essentially the average length of the projections of K n . It is still an open problem to determine the exact rate of decay of this average. Until recently, the only explicit upper bound exp(- log_* n) was due to Peres and Solomyak. (log_* n is the...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Fedor Nazarov
Microsoft Research Video
movies
eye 29
favorite 0
comment 0
The cover time of a finite graph G (the expected time for simple random walk to visit all vertices) has been extensively studied, yet a number of fundamental questions concerning cover times have remained open: Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to an O(1) factor; Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution of the walk is within a factor of 2, say, of the stationary...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Yuval Peres
Microsoft Research Video
movies
eye 32
favorite 0
comment 0
The notable KKL Theorem of Kahn, Kalai, and Linial says that if f : 0,1 n - 0,1 is a balanced boolean function, then there is at least one coordinate i with "influence" at least Omega(log n / n).We generalize this result to boolean functions on Cayley and Schreier graphs, whenever the generating set is a union of conjugacy classes and the associated Markov chain has a good log-Sobolev constant. E.g., we show that if f is a balanced Boolean function on the set of n-bit strings with...
Topics: Microsoft Research, Microsoft Research Video Archive, Yuval Peres, Ryan O'Donnell